﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0105_CountPrimes : IAlgorithm
    {
        // 计数质数

        // 统计所有小于非负整数 n 的质数的数量。

        // 提示：
        //   0 <= n <= 5 * 10^6
        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(CountPrimes());
        }

        // 算法
        // 埃拉托斯特尼 埃氏筛选法
        public int CountPrimes(int n)
        {
            bool[] arr = new bool[n];
            int cnt = 0;
            for (int i = 2; i < n; i++)
            {
                if (arr[i])
                    continue;
                cnt++;
                for (int j = i; j < n; j += i)
                    arr[j] = true;
            }
            return cnt;
        }
    }
}
